﻿using System.Collections.Generic;

namespace SortAndDatastruct {
    /// <summary>
    /// 计数排序算法，使用数组、词典两种数据结构实现。[需要额外空间]
    /// 线性排序,效率O(N)
    /// </summary>
    class CountingSort : ISort {
        private Dictionary<int, int> dic;
        /// <summary>
        /// 排序接口
        /// 默认排序范围-32768-32767内的整数
        /// 使用词典实现
        /// </summary>
        /// <param name="Array">带排序的数组</param>
        internal override void Sort(ref int[] Array) {
            if (Array == null || Array.Length < 2) return;
            CNTSort(ref Array, -32768, 32767);
        }
        /// <summary>
        /// 计数排序算法:使用了词典对象，使该算法具有一般性
        /// 弊病：仍然需要知道带排序的范围
        /// </summary>
        /// <param name="Array">需要排序的数组</param>
        /// <param name="Min">数组中最小的数</param>
        /// <param name="Max">数组中最大的数</param>
        /// <returns>有序数组</returns>
        private void CNTSort(ref int[] Array, int Min, int Max) {
            if (Array == null || Array.Length < 2 || Min > Max) return;
            dic = new Dictionary<int, int>();
            int[] bArr = new int[Array.Length];
            //初始化词典
            for (int i = Min; i <= Max; ++i) {
                dic[i] = 0;
            }
            for (int i = 0; i < Array.Length; ++i) {
                if (!dic.ContainsKey(Array[i])) return;// 如果在词典中无法找到该项，则认为范围设置错误
                dic[Array[i]] += 1;
            }
            for (int i = Min + 1; i <= Max; ++i) {
                dic[i] += dic[i - 1];
            }
            for (int i = Array.Length - 1; i >= 0; --i) {
                bArr[dic[Array[i]] - 1] = Array[i];//没有从1开始做索引，所以此处要减一
                dic[Array[i]] -= 1;
            }
            Array = bArr;
        }
        /// <summary>
        /// 计数排序的核心算法：数组实现
        /// 弊病：无法对负数进行排序
        /// </summary>
        /// <param name="Array">带排序的数组</param>
        /// <param name="Max">带排序的最大项的值</param>
        /// <returns>排序后的数组</returns>
        private void CNTSort(ref int[] Array, int Max) {
            if (Array == null || Array.Length < 2 || Max < 1 || Max > 32767) return;
            int[] cntArray = new int[Max];//.net 默认的初始化了计数数组，初始值为0
            int[] resultArr = new int[Array.Length];
            for (int i = 0; i < Array.Length; ++i) {
                cntArray[Array[i] - 1] += 1;
            }
            for (int i = 1; i < Max; ++i) {
                cntArray[i] += cntArray[i - 1];
            }
            for (int i = Array.Length - 1; i >= 0; --i) {
                resultArr[cntArray[Array[i] - 1] - 1] = Array[i];
                cntArray[Array[i] - 1] -= 1;
            }
            Array = resultArr;
        }
    }
}
